package com.liuzhilong.infrastructure.framework.algorithms.algorithms.sort.base;

import static com.liuzhilong.infrastructure.framework.algorithms.algorithms.sort.SortCommon.*;

/**
 * <h1>插入排序</h1>
 *<p>
 *     插入排序，遍历数据，类似于排扑克牌，内循环将当前的数据放该放的位置。
 *</p>
 * <p>
 *      选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大 且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行 排序要快得多。
 * </p>
 *
 * 数据量很小的话 使用插入排序可能比一些高级排序算法快。这个数据量一般在15一下。
 */
public class InsertionSort {

    public static final void sort(Comparable[] arrays) {
        for (int i = 0; i <arrays.length ; i++) {
            //内循还 从i 到 0，循环比较，如果arrays[j]<arrays[j-1],交换j和j-1
            //如果第一次的j最小，这个过程就像冒泡一样。
            for (int j = i; j >=1 && less(arrays[j],arrays[j-1]); j--) {
                exch(arrays,j,j-1);
            }
        }
    }

    /**
     * 对数组的某些部分进行插入排序。
     * @param arrays
     * @param start
     * @param end
     */
    public static final void sort(Comparable[] arrays,int start,int end) {
        for (int i = start; i <=end ; i++) {
            //内循还 从i 到 0，循环比较，如果arrays[j]<arrays[j-1],交换j和j-1
            //如果第一次的j最小，这个过程就像冒泡一样。
            for (int j = i; j >start && less(arrays[j],arrays[j-1]); j--) {
                exch(arrays,j,j-1);
            }
        }
    }


}
